{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Backtesting on Syntetic Data\n",
    "## Generate Stochastic Process\n",
    "* Characterize stochastic process using historical data\n",
    "* Require initial parameters: $\\{ P_{i, 0}, E_0 [P_{i, T_i}] \\}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Backtesting through Cross-Validation\n",
    "## Two Ways\n",
    "* In a narrow sense: to simulate the historical performance\n",
    "    * Simulate the historical performance of an investment strategy\n",
    "    * Also known as walk-forward\n",
    "* In a broader sense: to simulate the scenarios that did not happend\n",
    "    * Less known\n",
    "\n",
    "## The Walk-Forward (WF) Method\n",
    "* Advantages\n",
    "    * Clear historical interpretation\n",
    "    * History is a filtration\n",
    "    * Embargo is not needed\n",
    "* Disadvantage\n",
    "    * a single scenario is tested, which can lead to overfitting\n",
    "    * WF is not necessary representitive of future performance, which can lead bias\n",
    "    * The initial decisions are made on smaller portion of the total samples\n",
    "    \n",
    "## Cross Validation (CV) Method\n",
    "* Advantages\n",
    "    * Tests k alternative scenariors\n",
    "    * Decision is made on sets of equal size\n",
    "    * No warm-up subset\n",
    "* Disadvantages\n",
    "    * Like WF, there is one and only one forecast generated per observations\n",
    "    * No clear historical interpretation\n",
    "    * Leakage is possible\n",
    "    \n",
    "* The combinatorial purged cross-validation (CPCV) method\n",
    "    * Use combinatorial after splitting datasets into N folds\n",
    "    * Able to generate multiple paths\n",
    "    \n",
    "## Overfitting\n",
    "* WF has high variance due to small portion of the dataset for large portion of decisions\n",
    "* High variance leads to false discovery\n",
    "* CV leads to lower variance due to multiple paths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Danger of Backtesting\n",
    "## Typical Flaws\n",
    "* Survivorship bias\n",
    "    * Ignoring bankrupt and delisted\n",
    "* Look-ahead bias\n",
    "    * Using information that was not published at that moment\n",
    "* Storytelling\n",
    "    * Making up a story to explain random patterns\n",
    "* Data mining and data snooping\n",
    "    * Training the model on the testing set\n",
    "* Transaction costs\n",
    "    * The only way to be certain about transaction costs is interacting with trading book\n",
    "* Outliers\n",
    "* Shorting\n",
    "    * Requires finding a lender\n",
    "    * The cost of lending and the amount available is generally unkonwn\n",
    "\n",
    "## Overfitting\n",
    "* Multiple backtesting leads to selection bias\n",
    "* Should not tweak a model using backtest\n",
    "* General recommendations to avoid overfitting\n",
    "    * Develop models for entire asset classes or investment universe\n",
    "    * Apply Bagging\n",
    "    * Do not backtest until all research is complete\n",
    "    * Record every backtest conducted on a dataset so that the probability of backtest overfitting may be estimated\n",
    "    * Simulate scenarios rather than history\n",
    "    * If the backtest fails to identify a profitable strategy, start from scratch\n",
    "    \n",
    "## Probability of Overfitting\n",
    "1. Split data into S piecies\n",
    "2. Construct combination from S splits\n",
    "3. Choose optimal strategy \n",
    "4. Try the optimal strategy on test data and estimate relative rank\n",
    "5. Repeat 3. and 4. to get samples of relative ranks\n",
    "6. Calculate probability that the optimal strategy of in sample performs worse than median"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bet Sizing\n",
    "* Need to learn test statistics\n",
    "\n",
    "## Strategy Independent Approaches\n",
    "* Use concurrency of bets and fit with mixture of two Gaussians\n",
    "* Predict through ML algorithms\n",
    "\n",
    "## Approach from Predicted Probabilities\n",
    "* Normalize and use Gaussian's CDF\n",
    "\n",
    "## Dynamic Bet Sizes and Limit Prices\n",
    "* Adjust bet size depending on changes of current prices and predictions\n",
    "* The lager gap between the current price and prediction, the larger size you put\n",
    "* Set the bet size limit in advance\n",
    "\n",
    "## Regularization\n",
    "* Averaging active bets between t0 and t1\n",
    "* Discretize bets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hyperparameter Tuning\n",
    "## Search Method\n",
    "* Grid search\n",
    "* Random search: effective for searching in high dimensional space\n",
    "\n",
    "## Loss Function\n",
    "* F1: When using meta labeling\n",
    "* Negative log loss: Better than accuracy due to based on probability rather than prediction itself"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Feature Importance\n",
    "* Has to be dealt with before backtest\n",
    "* Figure out what features are important instead of cycling backtests\n",
    "* Substitution effects: importance is reduced when there are some other related features\n",
    "\n",
    "### MDI (Mean Decrease Impurity)\n",
    "* Tree based methods\n",
    "* Measured through impurity decreasing\n",
    "* In-Sample method\n",
    "* Every feature has somewhat importance\n",
    "\n",
    "### MDA (Mean Decrease  Accuracy)\n",
    "* Out-Of-Sample method\n",
    "* Any performance measure\n",
    "* Any kind of estimators\n",
    "* See the change by shuffling selected features\n",
    "\n",
    "### SFI (Single Feature  Importance)\n",
    "* Without substitution effects\n",
    "    * Substitution effects can lead us to wrong conclusion though not problem in prediction\n",
    "* Any estimators and performance measures\n",
    "* Use a single feature for each trial and see the defined score\n",
    "* Out-Of-Sample method\n",
    "* Fail in finding combination effects\n",
    "\n",
    "### Orthogonal Features\n",
    "* Alleviate the impact of linear substitution effects\n",
    "* Require centering and rescaling before applying\n",
    "* Not related to overfitting because of not looking at labels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cross Validation in Finance\n",
    "\n",
    "## Leakage\n",
    "* Data points are overlapped\n",
    "* Use a dataset multipletimes, which leads to overfitting\n",
    "* Two ways to avoid inflating validation score due to leakage\n",
    "    * Drop overlapped instances from training data\n",
    "    * Apply early stopping to base estimators and use bagging with sequential bootstrap\n",
    "* Shuffling inflates the performance due to simlarity among data instances\n",
    "\n",
    "## Purged K-Fold CV\n",
    "* Purging: Get rid of overlapped instances\n",
    "* Embargo:\n",
    "    * Get rid of training data immediately after test data\n",
    "    * Before purging"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ensemble\n",
    "## Three Sources of Errors\n",
    "* Bias\n",
    "    * Caused by unrealistic assumption\n",
    "    * Underfitting\n",
    "* Variance\n",
    "    * Caused by sensitivity to small changes in the training set\n",
    "    * Overfitting\n",
    "* Noise\n",
    "    * Caused by the variance of observed values\n",
    "    * Irreducible errors\n",
    "\n",
    "\n",
    "## Boosting\n",
    "* Reduce bias\n",
    "* Resilient to overfitting\n",
    "* Iterate the following steps:\n",
    "    * Estimate error from the current estimator (Weights errors according to errors of previous models)\n",
    "    * Learn weak learner to minimize error\n",
    "    * Add a new learned model to the estimator with an optimal coefficient\n",
    "* Gradient Boosting\n",
    "    * Generic version of boosting, applicable for any loss functions\n",
    "    * Require analytical derivative of loss function with respect to estimator\n",
    "    * Generalize gradient by learned weak learners => Try to predict gradient with a new weak learner\n",
    "    \n",
    "## Bootstrap\n",
    "* Reduce varaince\n",
    "* Reduce bais for classifiers bettera than chance with large samples \n",
    "* Unable to improve poor performance classifiers\n",
    "* The less correlated esimatores, the more you can reduce in bias\n",
    "* Simlar out-of-bag in finacial applciation => strong correlcation\n",
    "* Sequential bootstrap is alterantive solution\n",
    "* Random Forest: Use second level randomness, use sampled subset of features\n",
    "\n",
    "## Boosting with Samples\n",
    "1. Subsamples training data according to certain weights\n",
    "2. Train an estimator\n",
    "3. If the learned estimator achives accuracy better than the threshold, acceot the esimator. Otherwise, go back to 1\n",
    "4. Update weights by giving more weights to misclassified observations\n",
    "5. Repeat 1-4 till getting N estimators\n",
    "6. Aggregate trees\n",
    "\n",
    "## Bagging vs Boosting\n",
    "* Boosting has the risk of fitting which is most cared in finance context => Bagging is prefered in financial context\n",
    "* Boosting is sequential while bagging can be parallelized\n",
    "* Bagging is able to make non-scalable algorithm scalable by utilizing early stopping"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stationarity\n",
    "### Definition\n",
    "* Strictly Stationary: If the joint distribution of that of $X_{t_1}, \\dots, X_{t_k}$ is the same as $X_{t_1 + \\tau}, \\dots, X_{t_k + \\tau}$ for all $t_1, \\dots, t_k, \\tau$\n",
    "* Random walk is not stationary. Its difference is stationary.\n",
    "\n",
    "### MA Process\n",
    "* $X_t = \\beta_0 Z_t + \\beta_1 Z_{t-1} + \\cdots + \\beta_q Z_{t - q}$\n",
    "* Invertible: $Z_t = \\sum_{j=0}^\\infty \\pi_j X_{t - j}$\n",
    "* Let $B^j X_t = X_{t - j}$,\n",
    "$$X_t = (\\beta_0 + \\beta_1 B + \\cdots + \\beta_q B^q) Z_t = \\theta (B) Z_t$$\n",
    "* If the roots of $\\theta(B) = 0$ lies outside the unit circle, its invertible.\n",
    "Simply because\n",
    "$$(B - \\lambda)^{-1} = -\\frac{1}{\\lambda} (1 - \\frac{B}{\\lambda})^{-1}$$\n",
    "Its Taylor expansion converges if $\\lambda$ is larger than 1.\n",
    "\n",
    "###  AR Process\n",
    "* $X_t = \\alpha_1 X_{t - 1} + \\cdots + \\alpha_p X_{t - p} + Z_t$\n",
    "* $Z_t = (1 - \\alpha_1 B - \\cdots - \\alpha_p B^p) X_t = \\phi(B) X_t$\n",
    "* In the same way as MA, if the root of $\\phi(B)$ lies outside the unit circle, the process is invertible, which implies that the process maybe stationary.\n",
    "* Non unit roots is sufficient condition of stationarity\n",
    "* A unit root is necessary condition for stationarity\n",
    "\n",
    "### Dickey-Fuller Test\n",
    "* Reference, https://en.wikipedia.org/wiki/Dickey%E2%80%93Fuller_test\n",
    "* Test if the AR process is stationary <=> test if a unit root is present\n",
    "* For AR(1): $y_t = \\rho y_{t-1} + u_t$ => $\\Delta y_t = (\\rho - 1) y_{t-1} + u_t = \\delta y_{t-1} + u_t$\n",
    "* Check if $\\delta$ is equivalent to 0\n",
    "* Tests:\n",
    "    * $\\Delta y_t = \\delta y_{t-1} + u_t$\n",
    "    * With drift: $\\Delta y_{t-1} = \\alpha_0 + \\delta y_{t-1} + u_t$\n",
    "    * With drift and deterministic time trend: $\\Delta y_t = \\alpha_0 + \\alpha_1 t + \\delta y_{t-1} + u_t$\n",
    "* Use Dickey-Fuller table\n",
    "\n",
    "### Augmented Dicky-Fuller  Test\n",
    "* Reference, https://en.wikipedia.org/wiki/Augmented_Dickey%E2%80%93Fuller_test\n",
    "* Test if a unit root is present\n",
    "* $\\Delta y_t = \\alpha + \\beta t + \\gamma y_{t-1} + \\delta_1 \\Delta y_{t-1} + \\cdots + \\delta_{p-1} \\Delta y_{t- p + 1} + u_t$\n",
    "* Null Hypothesis: $\\gamma = 0$ => Non stationary\n",
    "* Alternative Hypothesis: $\\gamma < 0$ => Stationary\n",
    "* Test Statistics: $DF = \\frac{\\hat{\\gamma}}{SE(\\hat{\\gamma})}$\n",
    "\n",
    "### Integration of order d\n",
    "* If $(1 - B)^d X_t$ is stationary process, X has the integration of order d\n",
    "* Co-integration: A linear combination leads to lower order of integration\n",
    "* Engle–Granger co-integration test:\n",
    "    * Estimate coefficients by OLS: $y_t - \\hat{\\beta} x_t = u_t$\n",
    "    * Check if $u_t$ is stationary by Dickey-Fuller test\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Multiprocessors\n",
    "## Parallelism\n",
    "* Multithreading: Run more than one threads under the same core\n",
    "* Multiprocessing: Run on more than one cores\n",
    "* GIL (Global Interpreter Lock) assigns write access to one thread per core => Python parallelize through multiprocessing\n",
    "* Atom: Single task\n",
    "* Molecule: Subset of tasks\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sample Weights\n",
    "## Overlapping Outcomes\n",
    "* Range of samples could overlap to each other => Not IID\n",
    "* Consider the following properties:\n",
    "    * Number of concurrent labels: how many labels uses data at a certain time, i.e., $c_t = \\sum_{i=1}^I 1_{t, i}$\n",
    "    * Uniqueness: $u_{t, i} = 1_{t, i} / c_t$\n",
    "    * Average uniqueness of a label: uniqueness averaging over from 1 to T, i.e., $\\bar{u}_i = (\\sum_t u_{t, i}) / (\\sum_t 1_{t, i})$\n",
    " \n",
    "## Bagging Classifiers and Uniqueness\n",
    "* Assuming IID leads to oversampling\n",
    "* Let $\\bar{u}$ be a average uniqueness\n",
    "* If $I^{-1} \\sum_{i=1}^I \\bar{u}_i << 1$,\n",
    "    * Redundant to each other\n",
    "    * Very similar to out-of-bag\n",
    "* Solutions:\n",
    "    * Drop overlapping outcomes => extreme loss of information\n",
    "    * Lower maximum number of samples\n",
    "* [Sequential Bootstrap](https://ac.els-cdn.com/S0378375897000414/1-s2.0-S0378375897000414-main.pdf?_tid=c9bde38a-9f30-43ca-abcf-98033c135788&acdnat=1529805932_882bdfdde2acf41470f32510b3a5a03c)\n",
    "* Variation of Sequential Bootstrap\n",
    "    * $\\bar{u}_j^{(i+1)} = 1_{t, j} (1 + \\sum_{k \\in \\phi^{(i)}} 1_{t, k})^{-1}$\n",
    "    * Resample with adapted weights: $\\delta_j^{(i)} = \\bar{u}_j^{(i)} (\\sum_{k=1}^I \\bar{u}_k^{(i)})^{-1}$\n",
    "    * After every samaple, update weights\n",
    "    * The process is repeated until $I$ draws\n",
    "    \n",
    " \n",
    "## Prioritized Sampling\n",
    "* Return Attribution: Assign weight for training according to the value of returns\n",
    "* Time Decay: prioritized decay linearly as data becomes old\n",
    "* Class Weights: Make different prioritization among classes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Labeling\n",
    "\n",
    "## Fixed-Time Horizon Method\n",
    "* Fixed threshold\n",
    "* Time bar\n",
    "* Not take into consideration the change of scale\n",
    "* To improve:\n",
    "    * Label per a varying threshold depending on estimated $sigma_t$\n",
    "    * Use dollar or volume based bars\n",
    "\n",
    "## The Triple-Barrier Method\n",
    "* Three thresholds\n",
    "    * Touching Upper: label 1\n",
    "    * Touching Lower: label -1\n",
    "    * Touching Vertical: 0 or sign of return\n",
    "    \n",
    "## Side and Size Label\n",
    "* Need to define side to determine the direction of profit taking and stop loss\n",
    "* Need algorithms to produce the side of transactions\n",
    "* We do not want to learn the side with a single ML model\n",
    "    * Primary model: Decide the side of your bets (Meta Labeling)\n",
    "    * Secondary model: Decide the side of bets\n",
    "    \n",
    "## Meta Labeling\n",
    "* Similar to model stacking\n",
    "* Helpful to achieve higher F1-scores\n",
    "    * Primary Model: Determine the side with high recall\n",
    "    * Secondary Model: Determine if you act or pass, focus on improving precision\n",
    "* Powerful with four reasons\n",
    "    1. White box\n",
    "        * Allows you to build a model on top of white box like fundamental models\n",
    "        * Helpful for quantamental firms\n",
    "    2. Avoids overfitting\n",
    "    3. More sophisticated model\n",
    "        * E.g., allows you to build a model focusing on long or short positions \n",
    "    4. Able to divide decisions depending on the bet size\n",
    "        * High accuracy on small bets and low accuracy on large bets ruins you\n",
    "* You can add a meta-labeling layer to any primary model\n",
    "* Drop under-populated labels\n",
    "    * ML algorithms do not perform well on too imbalanced classes\n",
    "    * scikit-learn bug"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Financial Data Structures\n",
    "## Types of Data\n",
    "* Fundamental Data\n",
    "* Market Data\n",
    "* Analytics\n",
    "* Alternative Data\n",
    "\n",
    "## Bars\n",
    "### Standard Bars\n",
    "* Time Bars: Sampled with fixed time interval\n",
    "* Tick Bars: Sampled with fixed number of ticks\n",
    "* Volume Bars: Sampled with fixed volume\n",
    "* Dollar Bars: Sampled with fixed amount of value\n",
    "\n",
    "### Information-Driven Bars\n",
    "* Use the followings to estimate the amount of information\n",
    "    * $b_t = \\begin{cases}\n",
    "        b_{t-1} if \\Delta p_t = 0\\\\\n",
    "        \\frac{\\Delta p_t}{| \\Delta p_t| } if \\Delta p_t \\neq 0\n",
    "      \\end{cases} $\n",
    "    * $T^* = \\underset{T}{arg min} \\{|\\theta_T| \\geq E[\\theta_T]\\}$ for defined $\\theta_T$\n",
    "* Tick Imbalanced Bars (TIB)\n",
    "    * Take into consideration how many times prices changes\n",
    "    * $\\theta_T = \\sum_{t=1}^T b_t$\n",
    "    * Look at flow imbalance. If imbalance is more than expected, make a new bar\n",
    "* Volume/Dollar Imbalanced Bars (VIB and DIB)\n",
    "    * $\\theta_T = \\sum_{t=1}^T b_t v_t$\n",
    "* Tick Runs Bars\n",
    "    * Monitor the sequence of buys\n",
    "    * $\\theta_T = max\\{ \\sum_{t|b_t=1}^T b_t, - \\sum_{t|b_t=-1}^T b_t\\}$\n",
    "* Volume/Dollar Runs Bars\n",
    "    * $\\theta_T = max\\{ \\sum_{t|b_t=1}^T b_t v_t, - \\sum_{t|b_t=-1}^T b_t v_t\\}$\n",
    "    \n",
    "## Dealing with Multi-Product Series\n",
    "* Example cases:\n",
    "    * Model spreads with changing weights\n",
    "    * Basket of securities where dividends/coupons must be reinvested\n",
    "    * Basket that must be rebalanced\n",
    "    * Index whose constitutes changed\n",
    "    * Replace an expired/matured contract/security\n",
    "* Goal is to transform any complex multi-product dataset into a single dataset that resembles a total-return ETF\n",
    "\n",
    "### ETF Trick\n",
    "* Problems when trading a spread of futures\n",
    "    * The spread is characterized by a vector of weights changing over time and may converge.\n",
    "    * Spreads can be negative values\n",
    "    * Trading times  will not align exactly for all constituents\n",
    "* The goal is to model a basket of future as if it was a single non-expiring cash product\n",
    "    * Changes in the series reflects PnL\n",
    "    * Strictly positive\n",
    "    * Shortfall is taken into consideration\n",
    "    \n",
    "##### Method\n",
    "For instrument $i = 1, \\dots, I$ at bar $t = 1, \\dots, T$\n",
    "* $o_{i, t}$: Raw open price\n",
    "* $p_{i, t}$: Raw close price\n",
    "* $\\phi_{i, t}$: Exchange rate to USD\n",
    "* $v_{i, t}$: Volume\n",
    "* $d_{i, t}$: Dividend or coupon\n",
    "    \n",
    "For allocation vector $\\omega_t$ rebalanced on bars $B \\subseteq \\{1, \\dots, T\\}$,\n",
    "* $h_{i, t} = \\begin{cases}\n",
    "        \\frac{\\omega_{i, t} K_t}{o_{i, t + 1} \\phi_{i, t} \\sum_i |\\omega_{i, t}|} if t \\in B\\\\\n",
    "        \\frac{\\Delta p_t}{| \\Delta p_t| } if \\Delta p_t \\neq 0\n",
    "      \\end{cases} $\n",
    "      \n",
    "\n",
    "## Sampling Features\n",
    "* Not all of ML algorithms are scalable, e.g., SVM\n",
    "* ML works well when trained on relevant features\n",
    "* Event-Based Sampling: Sample feature relevant to certain events, e.g., spike of volatility\n",
    "    * CUSUM (Cumulative Sum) Filter: Sample when target value deviates larger than defined threshold"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
